package com.lw.leetcode.tree.b;

import com.lw.leetcode.linked.ListNode;

/**
 * 147. 对链表进行插入排序
 *
 * @Author liw
 * @Date 2021/4/29 16:25
 * @Version 1.0
 */
public class InsertionSortList {
    public static void main(String[] args) {
        InsertionSortList test = new InsertionSortList();
        ListNode listNode = test.insertionSortList(ListNode.getInstance2());
        System.out.println(listNode);
    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode a = new ListNode(Integer.MIN_VALUE);
        ListNode b;
        a.next = head;
        ListNode item = head.next;
        ListNode l = head;
        while (item != null) {
            ListNode next = item.next;
            b = a;
            boolean flag = true;
            while (b != item) {
                if (item.val < b.next.val) {
                    l.next = next;
                    item.next = b.next;
                    b.next = item;
                    flag = false;
                    break;
                }
                b = b.next;
            }
            if (flag) {
                l = l.next;
            }
            item = next;
        }
        return a.next;
    }

}
